//--------------------------------------------------------------------------------------//
//                                                                                      //
//    __  __  __    __    __  ___   __   ___  __    ___    __  __  __  ___  ___  __     //
//   / _)/  \(  )  (  )  (  )(   \ (  ) (  ,)(  )  (  _)  (  \/  )/  \(   \(  _)(  )    //
//  ( (_( () ))(__  )(__  )(  ) ) )/__\  ) ,\ )(__  ) _)   )    (( () )) ) )) _) )(__   //
//   \__)\__/(____)(____)(__)(___/(_)(_)(___/(____)(___)  (_/\/\_)\__/(___/(___)(____)  //
//                                                                                      //
//                                                                                      //
//       Copyright by Theodor Mader, 2009                                               //
//			www.theomader.com/public/Projects.html                                      //
//--------------------------------------------------------------------------------------//


#include "Geometry.h"
#include "threading.h"

#include <list>
#include <vector>
#include <fstream>


struct BspNode 
{
	Geometry::Plane separatingPlane;
	BspNode *pos, *neg;

	BspNode( const Geometry::Plane& separatingPlane );
	BspNode() { pos = 0; neg = 0; }
};


class BspTree 
{
	friend DWORD __stdcall Threading::ProcessTasksWorker( LPVOID taskData );

private:
	BspNode* m_pRoot;
	const std::vector<Geometry::Vertex>& m_Vertices;
	unsigned int m_iNumVerticesPerLeaf;

public:
	BspTree( const std::vector<Geometry::Vertex>& vertices, unsigned int numVerticesPerLeaf ); 
	~BspTree();

	//! starts creating the tree
	void Build();
	void BuildMT( unsigned int numThreads );

	//! writes the bsp tree to \a fileName
	bool SaveToFile( std::string fileName );

	//! writes the bsp tree to \a buffer
	bool SaveToBuffer( char* destination, unsigned long size );

	//! computes the total number of nodes in the tree (including leafs)
	unsigned int CountNodes() { return NumNodes( m_pRoot ); }

	//! computes the total number of leafs in the tree
	unsigned int CountLeafs() { return NumLeafs( m_pRoot ); }

	//! computes the required buffer size for storing the tree
	unsigned int ComputeRequiredBufferSize() { return RequiredBufferSize( m_pRoot ); }

private:

	//! recursively writes planes of bsp nodes to \a file (tree is traversed in inorder!)
	void RecWriteToStream( std::ostream& stream, const BspNode& node );

	//! recursively writes planes of bsp nodes to \a buffer, at \a position (tree is traversed in inorder!)
	void RecWriteToBuffer( char *buffer, unsigned long& position, const BspNode& node, unsigned long size );


	//! computes a subtree for all vertices indexed by \a indices, returns the root node
	void BuildSubtree( Threading::Task& task );

	static std::list<Threading::Task*> BuildNode( Threading::Task& task, const std::vector<Geometry::Vertex>& vertices, const unsigned int numVerticesPerLeaf );

	void DeleteTree( BspNode*& root );

	//! returns the number of nodes the tree contains starting at \a node
	unsigned long NumNodes( BspNode* node );

	//! returns the number of leafs the tree contains starting at \a node
	unsigned long NumLeafs( BspNode* node );

	//! returns the required buffer size to store the tree starting at \a node
	unsigned long RequiredBufferSize( BspNode* node );
};


